//Sat Jun  4 15:45:49 CDT 2011
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

class WordFind {
public:
	vector <string> findWords(vector <string>, vector <string>);
	bool checkRow(vector<string>, int, int, string);
	bool checkCol(vector<string>, int, int, string);
	bool checkDia(vector<string>, int, int, string);
};

bool WordFind::checkRow(vector<string> grid, int x, int y, string ptrn){
	int N = ptrn.size();
	if(y+N <= grid[0].size()){
		return grid[x].substr(y, N) == ptrn;
	}
	else return false;
	return false;
}

bool WordFind::checkCol(vector<string> grid, int x, int y, string ptrn){
	int N = ptrn.size();
	if(x+N <= grid.size()){
		for(int i=x; i<x+N; i++){
			if(ptrn[i-x] != grid[i][y]) return false;
		}
	}
	else return false;
	return true;
}

bool WordFind::checkDia(vector<string> grid, int x, int y, string ptrn){
	int N = ptrn.size();
	if(x+N <= grid.size() && y+N <= grid[0].size()){
		for(int i=0; i<N; i++){
			if(ptrn[i] != grid[x+i][y+i]) return false;
		}
	}
	else return false;
	return true;
}

vector <string> WordFind::findWords(vector <string> grid, vector <string> wordList) {
	vector<string> p;
	int M = grid.size();
	int N = grid[0].size();
	for(int k=0; k<wordList.size(); k++){
		bool flag = true;
		for(int i=0; i<M && flag; i++){
			for(int j=0; j<N && flag; j++){
				if(checkRow(grid, i, j, wordList[k]) || checkCol(grid, i, j, wordList[k]) || checkDia(grid, i, j, wordList[k])){
					stringstream s;
					s << i << " " << j;
					p.push_back(s.str());
					flag = false;
				}
			}
		}
		if(flag)
			p.push_back("");
	}
	return p;
}


//Powered by [KawigiEdit] 2.0!
